136 - Ugly numbers/136.cpp

   1 #include <iostream>
   2 #include <queue>
   3
   4 using namespace std;
   5
   6 typedef unsigned long long ull;
   7
   8 ull h[1501];
   9
  10 priority_queue<ull, vector<ull>, greater<ull> > q;
  11
  12 int main(){
  13
  14   q.push(1);
  15   int i=1;
  16   while (i <= 1500){
  17     ull top = q.top();
  18     q.pop();
  19     h[i++] = top;
  20
  21     q.push(top*2);
  22     if (top % 2 != 0) {
  23       q.push(top*3);
  24     }
  25     if (top % 2 != 0 && top % 3 != 0){
  26       q.push(top*5);
  27     }
  28     //    if (top % 2 != 0 && top % 3 != 0 && top % 5 != 0){
  29     //q.push(top*7);
  30   }
  31   //cout << q.size() << endl;
  32   //int n;
  33   //while (cin >> n && n > 0) cout << h[n] << endl;
  34   cout << "The 1500'th ugly number is " << h[1500] << ".\n";
  35   return 0;
  36 }